package com.example.leetcode.prcatice;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个数组 nums ，将其划分为两个连续子数组 left 和 right， 使得：
 *
 * left 中的每个元素都小于或等于 right 中的每个元素。
 * left 和 right 都是非空的。
 * left 的长度要尽可能小。
 * 在完成这样的分组后返回 left 的 长度 。
 *
 * 用例可以保证存在这样的划分方法。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/partition-array-into-disjoint-intervals
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test915 {

    public int partitionDisjoint(int[] nums) {
        int len = nums.length;
        int[] t = new int[len + 10];
        t[len -1] = nums[len -1];
        for (int i = len -2; i>=0;i--) {
            // 最小后缀和
            t[i] = Math.min(t[i + 1],nums[i]);
        }
        int max = Integer.MIN_VALUE;
        for (int i  =0 ;i<len;i++) {
            max = Math.max(nums[i],max);
            if (max <= t[i + 1]) {
                return i+ 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Test915 t = new Test915();
        int[] nums = {5,0,3,8,6};
        System.out.println(t.partitionDisjoint(nums));
    }
}
